package com.nl.math;

public class UglyNumber {

	
	//因数只有２３５
	//下一个丑数一定是前几个丑数乘以２，３，５的结果
	public static int uglyNumber(int index){
		if(index<1){
			return -1;
		}

		// 根据之前的丑数生成新的丑数,减少不必要的运算
		int[] uglys = new int[index];
		uglys[0] =1;
		int index2=0,index3=0,index5=0;
		int currentIndex = 1;
		
		while(currentIndex<index){
			//找到乘２，乘３，乘５的最小值，放入到数组中
			uglys[currentIndex] = Math.min(uglys[index2]*2, Math.min(uglys[index3]*3, uglys[index5]*5));

			//比当前最大值小的都pass掉，大的扔进去
			while(uglys[index2]*2<=uglys[currentIndex]){
				index2++;
			}
			//比当前最大值小的都pass掉，大的扔进去
			while(uglys[index3]*3<=uglys[currentIndex]){
				index3++;
			}
			//比当前最大值小的都pass掉，大的扔进去
			while(uglys[index5]*5<=uglys[currentIndex]){
				index5++;
			}
			currentIndex++;
		}
		return uglys[currentIndex-1];
	}
	
	public static void main(String[] args) {
		for(int i=0;i<10;i++){
			System.out.print(uglyNumber(i+1)+" ");
		}
	}
}
